package practise;


class Solution {
    /**
     * 由于*号是向后增长的，所以确定的状态只能从后边找
     * dp[i][j] 表示 text[i:] 和 pattern[j:] 是否能够匹配
     */
    public boolean isMatch(String text, String pattern) {
        int slen = text.length(), plen = pattern.length();
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        dp[slen][plen] = true;
        char[] chs = text.toCharArray(), chp = pattern.toCharArray();

        for (int i = slen; i >= 0; i--) {
            for (int j = plen - 1; j >= 0; j--) {
                boolean firstMatch = (i < slen &&
                        (chp[j] == chs[i] || chp[j] == '.'));
                if (j + 1 < plen && chp[j + 1] == '*') {
                    dp[i][j] = dp[i][j + 2] ||
                            i < slen && dp[i + 1][j] && firstMatch;
                } else
                    dp[i][j] = firstMatch && dp[i + 1][j + 1];
            }
        }
        return dp[0][0];
    }
}